package com.yoshino.leetcode.interview150.merge;

import java.util.Collections;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
    }

    public ListNode sortList(ListNode head) {
        // 归并，一直划分到最小单元，然后合并
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            // 无需排序
            return head;
        }
        // 找到中位数
        ListNode slow = head, fast = head.next.next, l, r;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 对右边进行排序
        r = mergeSort(slow.next);
        // 切断
        slow.next = null;
        l = mergeSort(head);
        // 合并
        return mergeList(l, r);
    }

    private ListNode mergeList(ListNode l, ListNode r) {
        ListNode root = new ListNode(), cur = root;
        // 排序，上面得到的一定是有序的
        while (l != null && r!= null) {
            if (l.val < r.val) {
                cur.next = l;
                l = l.next;
            } else {
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        cur.next = l == null ? r : l;
        return root.next;
    }

    public Node construct(int[][] grid) {
        return quadTree(grid, 0, 0, grid.length);
    }

    private Node quadTree(int[][] grid, int x, int y, int offset) {
        if (offset <= 0) {
            return null;
        }
        for (int i = x; i < x + offset; i++) {
            for (int j = y; j < y + offset; j++) {
                // 在此区域中存在不相等情况，只有 0 1
                if (grid[i][j] != grid[x][y]) {
                    return new Node(true, false,
                            quadTree(grid, x, y, offset / 2),
                            quadTree(grid, x, y + offset / 2, offset / 2),
                            quadTree(grid, x + offset / 2, y, offset / 2),
                            quadTree(grid, x + offset / 2, y + offset / 2, offset / 2)
                            );
                }
            }
        }
        // 该区域都一致
        return new Node(grid[x][y] == 1, true);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        // 分冶
        if (left == right) {
            // 只有一条已经是排序好的
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l = merge(lists, left, mid);
        ListNode r = merge(lists, mid + 1, right);
        return mergeTwoList(l, r);
    }

    private ListNode mergeTwoList(ListNode l, ListNode r) {
        ListNode root = new ListNode(), cur = root;
        while (l != null && r != null) {
            if (l.val < r.val) {
                cur.next = l;
                l = l.next;
            } else {
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        cur.next = l == null ? r : l;
        return root.next;
    }
}